<!DOCTYPE html>
<html>

<head>
  <meta charset="UTF-8">
  <title>搜索算法</title>
  <script src="../help/help.js"></script>
  <link rel="stylesheet" href="../code-view/code.css">
  <script src="../code-view/code.js"></script>
  <style>
    #content {
      text-align: center;
      color: #ccc;
    }

    #content ul {
      margin: 0px;
      padding: 0;
      display: inline-block;
      white-space: pre;
    }

    #content li {
      display: inline-block;
      height: 40px;
      width: 40px;
      border: 1px solid #ccc;
      vertical-align: top;
      border-radius: 9px;
      line-height: 40px;
      background-color: #eee;
    }

    #content li.count {
      background-color: red;
    }

    #content li.end {
      background-color: blue;
    }

    #content li.start {
      background-color: yellow;
    }

    #content li.dang {
      background-color: green;
    }

    #content li.road {
      background-color: cyan;
    }

    [code] {
      width: 80%;
      margin: auto;
    }
    .center {
      text-align: center;
    }
    button {
      border: #ccc;
      line-height: 24px;
      margin: 20px;
      padding: 3px 8px;
      border-radius: 8px;
    }
  </style>
</head>

<body>
  <div id="content"></div>
  <div class="center">
    <button id="deep">深度搜索</button>
    <button id="breadth">宽度搜索</button>
  </div>
  <h3 class="center">代码如下</h3>
  <script code="4">
    var html = '';
    var line = 20;
    var col = 30;

    for (var y = 0; y < line; y++) {
      html += '<ul>'
      for (var x = 0; x < col; x++) {
        html += '<li title="' + y + '-' + x + '"></li>'
      }
      html += '</ul>'
    }

    $('#content').html(html).on('click', 'li', function (e, el) {
      var x = $(el).index();
      var y = $(el).parent().index();
      if (!$(el).hasClass()) {
        $(el).addClass('dang');
        disables.push([y, x]);
      }
    });

    var start = [8, 3],
      end = [13, 25],
      li = $('#content').find('li'),
      disables = [];

    for (var i = 0; i < disables.length; i++) {
      var step = disables[i]
      li.eq(step[0] * col + step[1]).addClass('dang');
    }

    li.eq(start[0] * col + start[1]).addClass('start').html('start')
    li.eq(end[0] * col + end[1]).addClass('end').html('end')

    $('#deep').on('click', function () {
      DeepFirstSearch(start, end, function (found) {
        if (found) {
          while (found) {
            li.eq(found[0] * col + found[1]).addClass('road')
            found = found.pre
          }
        } else {
          console.log('not find')
        }

      }, function (step, count) {
        li.eq(step[0] * col + step[1]).addClass('count').html(count)
      })
    });

    $('#breadth').on('click', function () {
      BreadthFirstSearch(start, end, function (found) {
        if (found) {
          while (found) {
            li.eq(found[0] * col + found[1]).addClass('road')
            found = found.pre
          }
        } else {
          console.log('not find')
        }

      }, function (step, count) {
        li.eq(step[0] * col + step[1]).addClass('count').html(count)
      })
    });

    function DeepFirstSearch(start, end, fn, handleStep) {
      /*
        0 起点
        -1 没探索过的地方
        -2 终点
        -3 障碍物
        > 0 步数
      */
      var map = []
      for (var j = 0; j < line; j++) {
        var b = [];
        map.push(b)
        for (var i = 0; i < col; i++) {
          b.push(-1)
        }
      }

      for (var o = 0; o < disables.length; o++) {
        var dis = disables[o]
        map[dis[0]][dis[1]] = -3;
      }

      map[start[0]][start[1]] = 0;
      map[end[0]][end[1]] = -2;

      function handle(j, i, next, count, pre) {
        if (map[j]) {
          var step = [j, i];
          step.pre = pre;
          if (map[j][i] === -1) {
            map[j][i] = count;
            next.push(step)
            handleStep && handleStep(step, count)
          } else if (map[j][i] === -2) {
            return step;
          }
        }
      }

      function findNext(now, count) {
        var next = [];
        count++
        var len = now.length;
        if (len) {
          for (var m = 0; m < len; m++) {
            var poi = now[m]
            var y = poi[0];
            var x = poi[1];
            var found = handle(y, x + 1, next, count, poi) ||
              handle(y + 1, x, next, count, poi) ||
              handle(y, x - 1, next, count, poi) ||
              handle(y - 1, x, next, count, poi)
            // || handle(y + 1, x + 1, next, count, poi)
            // || handle(y + 1, x - 1, next, count, poi)
            // || handle(y - 1, x - 1, next, count, poi)
            // || handle(y - 1, x + 1, next, count, poi)

            if (found) {
              fn && fn(found, count)
              return
            }
          }
          // next = next.sort(function(a, b) {
          //     return Math.pow(a[0] - end[0], 2) + Math.pow(a[1] - end[1], 2) - Math.pow(b[0] - end[0], 2) - Math.pow(b[1] - end[1], 2);
          // })
          // setTimeout(function() {
          findNext(next, count)
          // }, 33)
        } else {
          fn && fn(null, count)
        }

      }
      findNext([start], 0);
    }

    function BreadthFirstSearch(start, end, fn, handleStep) {
      /*
        0 起点
        -1 没探索过的地方
        -2 终点
        -3 障碍物
        > 0 步数
      */
      var map = []
      for (var j = 0; j < line; j++) {
        var b = [];
        map.push(b)
        for (var i = 0; i < col; i++) {
          b.push(-1)
        }
      }

      for (var o = 0; o < disables.length; o++) {
        var dis = disables[o]
        map[dis[0]][dis[1]] = -3;
      }

      map[start[0]][start[1]] = 0;
      map[end[0]][end[1]] = -2;

      function handle(j, i, next, count, pre, type) {
        if (map[j]) {
          var step = [j, i];
          step.pre = pre;
          step.type = type;

          if (map[j][i] === -1) {
            map[j][i] = count;
            next.push(step)
            handleStep && handleStep(step, count)
          } else if (map[j][i] === -2) {
            maxCount = count;
            return step;
          } else if (map[j][i] > 0 && count - 1 > map[j][i] + 1) {
            map[j][i] = map[j][i] + 1;
            fixed = true;
          } else if (map[j][i] > 0 && count - 1 < map[j][i] - 1) {
            map[j][i] = count;
            next.push(step)
            handleStep && handleStep(step, count)
          }
        }
      }
      var found = null
      var fixed;
      var maxCount = Infinity;

      function findNext(now, count) {
        var next = [];
        count++
        if (count >= maxCount) {
          return;
        }
        if (found) {
          return
        }
        var poi = now
        var y = poi[0];
        var x = poi[1];
        fixed = false;
        var some = handle(y, x + 1, next, count, poi, '右') ||
          handle(y + 1, x, next, count, poi, '下') ||
          handle(y, x - 1, next, count, poi, '左') ||
          handle(y - 1, x, next, count, poi, '上')
        // || handle(y + 1, x + 1, next, count, poi)
        // || handle(y + 1, x - 1, next, count, poi)
        // || handle(y - 1, x - 1, next, count, poi)
        // || handle(y - 1, x + 1, next, count, poi)
        if (some) {
          found = some
        }
        if (found) {
          return
        }
        if (fixed) {
          return
        }
        next = next.sort(function (a, b) {
          return Math.pow(a[0] - end[0], 2) + Math.pow(a[1] - end[1], 2) - Math.pow(b[0] - end[0], 2) - Math.pow(b[1] - end[1], 2);
        }).map(function (next) {
          findNext(next, count)
        });
      }
      findNext(start, 0);
      fn && fn(found, maxCount)
    }
  </script>
</body>

</html>